#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // bool tracebacking(string change_s, string &s, vector<string> &wordDict)
    // {
    //     if (change_s == s)
    //     {
    //         return true;
    //     }
    //     if (change_s.size() > s.size())
    //     {
    //         return false;
    //     }
    //     for (size_t i = 0; i < wordDict.size(); i++)
    //     {
    //         if (tracebacking(change_s + wordDict[i], s, wordDict))
    //         {
    //             return true;
    //         }
    //     }
    //     return false;
    // }
    // bool wordBreak(string s, vector<string> &wordDict)
    // {
    //     string change_s;
    //     return tracebacking(change_s, s, wordDict);
    // }

    bool wordBreak(string s, vector<string> &wordDict)
    {
        unordered_set<string> set(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (size_t i = 1; i <= s.size(); i++)
        {
            for (size_t j = 0; j < i; j++)
            {
                string str = s.substr(j, i - j);
                if (set.find(str) != set.end() && dp[j])
                {
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

int main()
{
    string s = "leetcode";
    vector<string> WordDict{"leet", "code"};
    Solution sol;
    cout << sol.wordBreak(s, WordDict) << endl;
    return 0;
}